/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package BL;

/**
 *
 * @author Elessar
 */
import BE.*;
//import Metodos.TwoOpt.*;
import java.util.List;
//import java.io.*;
import java.util.ArrayList;

public class BLGRASP {
    //Variables procesamiento
    private int totalNodos;
    private int cantObligatorios;
    private List<Integer> nodosObligatorios;
    private List<BENodo> grafo = null;
    private int cantIteraciones;
    private double alpha;
    private BENodo nodoActual = null;
    private int idAnterior;
    private BENodo ultObligatorio = null;
    
    //Variable respuesta
    private List<BENodo> rptaGrasp = null;
    private List<BENodo> Optimo = null;
    
    private List<BENodo> RCL = new ArrayList <BENodo>();
    private List<Integer> listaRecorridos = new ArrayList<Integer>();

    //private List<Integer> bloqueados = new ArrayList<Integer>();
    //private int[] contador;
    private int regresoInicio = 0;

    
    //Constructor GRASP
    public BLGRASP(int totalNodos, int cantObligatorios,
                 List<Integer> nodosObligatorios, List<BENodo> grafo)
    {
        this.cantObligatorios = cantObligatorios;
        this.nodosObligatorios = nodosObligatorios;
        this.totalNodos = totalNodos;
        this.grafo = grafo;
        this.cantIteraciones = 0;
        this.alpha = 0.5;
        //Nodo actual se inicializa como la entrada del almacen
        this.nodoActual = grafo.get(0);

        //contador = new int[totalNodos];
    }
    
        
    public BENodo dameNodoRCL(BENodo nodoActual)
    {
        List<BENodo> nodosVecinos = nodoActual.getVecinos();
        List<BENodo> nodos = new ArrayList<BENodo>();
        int mejorRuta = 10000;
        int peorRuta = 0;
        int indiceRCL = 0;
        int index;

        //limpiando nodos bloqueados
        for (int j = 0;j<nodosVecinos.size();j++)
            if (//!bloqueados.contains(nodosVecinos.get(j).getIdNodo()) && 
                    !listaRecorridos.contains(nodosVecinos.get(j).getIdNodo())){
                //if (nodos2.get(j).getIdNodo()!=this.idAnterior && this.regresoInicio<1)
//                if (ultObligatorio!=null && !(nodos.contains(nodosVecinos.get(j)))){
//                    if (ultObligatorio.getX()<nodoActual.getX() && nodosVecinos.get(j).getX()<nodoActual.getX())
//                        nodos.add(nodosVecinos.get(j));
//                    if (ultObligatorio.getY()<nodoActual.getY() && nodosVecinos.get(j).getY()<nodoActual.getY())
//                        nodos.add(nodosVecinos.get(j));
//                    if (ultObligatorio.getX()>nodoActual.getX() && nodosVecinos.get(j).getX()>nodoActual.getX())
//                        nodos.add(nodosVecinos.get(j));
//                    if (ultObligatorio.getY()>nodoActual.getY() && nodosVecinos.get(j).getY()>nodoActual.getY())
//                        nodos.add(nodosVecinos.get(j));
//                }    
//                else 
                    nodos.add(nodosVecinos.get(j));
            }

//        if (nodos.isEmpty())
//            System.out.println("El nodo " + nodoActual.getIdNodo() + " no tiene vecinos habilitados");
//        if (nodos.isEmpty())
//            for (int j = 0;j<nodosVecinos.size();j++)
//                nodos.add(nodosVecinos.get(j));

        int auxDist = 0;
        //Obtener "menor" distancia
        for (int i = 0;i<nodos.size();i++)
        {
            if (nodos.get(i).getIdNodo() != idAnterior){            
                auxDist = nodos.get(i).getDist();
                if (mejorRuta > auxDist && auxDist != 0)
                    mejorRuta = auxDist;
            }
        }
            
        //Obtener "mayor" distancia
        for (int i = 0;i<nodos.size();i++)
        {   
            if (nodos.get(i).getIdNodo()!=idAnterior){
                auxDist = nodos.get(i).getDist();
                if (peorRuta < auxDist && auxDist != 0)
                    peorRuta = auxDist;
            }
        }
        
        //Obtener lista RCL
        //int[] indicesRCL = new int[nodoActual.getVecinos().size()]; //peor de los casos
        //tenga los mismo que vecinos
        RCL.clear();
        for (int i = 0;i<nodos.size();i++)
        {
            auxDist = nodos.get(i).getDist();
            if (auxDist >= mejorRuta && auxDist <= this.alpha *
                                       (peorRuta - mejorRuta) + mejorRuta)
                RCL.add(nodos.get(i));
        }

        //Escojer un indice aleatoriamente
        indiceRCL = aleatorio(RCL.size());
              
        //Devolvemos el hijo que corresponda a ese indice
        if (RCL.size()>0)            
            return RCL.get(indiceRCL);
        else { 
            //System.out.println("ERROR : " +nodoActual.getIdNodo()+" Recorrido:"+listaRecorridos.size());
            for (int j=0; j<nodosVecinos.size(); j++){
                index = listaRecorridos.indexOf(nodosVecinos.get(j).getIdNodo());
                if (index>-1 && nodosVecinos.get(j).getIdNodo()!=idAnterior)
                    listaRecorridos.remove(index);}
//                if (listaRecorridos.contains(nodosVecinos.get(j).getIdNodo()))
//                    listaRecorridos.remove(listaRecorridos.indexOf(nodosVecinos.get(j).getIdNodo()));
            //listaRecorridos.clear();
            //return nodosVecinos.get(0);
            //return dameNodoRCL(nodoActual);
            return null;
        }
    }

//    public boolean esObligatorio(String[] obligatorios, BENodo nodo)
//    {
//        boolean esta = false;
//        String nombre = ""+nodo.getIdNodo();
//
//        for (int i=0;i<obligatorios.length;i++)
//            if (nombre.equals(obligatorios[i]))
//            {
//                esta = true;
//                break;
//            }
//        return esta;
//    }

    public int dameTamanoLista(List<BENodo> nodos)
    {
        int tamano = 0;
        for(int i = 0;i<nodos.size();i++)
            tamano += nodos.get(i).getDist();
        return tamano;
    }

    public BENodo cambiaNodoActual(int id)
    {
        BENodo devolver = null;
        //implementar busqueda binaria!
        for(int i=0;i<this.grafo.size();i++)
            if (id == this.grafo.get(i).getIdNodo())
            {
                devolver = this.grafo.get(i);
                break;
            }
        return devolver;
    }

    public static int aleatorio(int max){
		return (int)(Math.random()*(max-0))+0;
    }

    
    public List<BENodo> run(double alp, int ni)
    {
        //Inicializar los parametros propios del GRASP
        //inicializarParametros();
        this.alpha=alp;
        this.cantIteraciones=ni;
        //Fase de Construccion
 
        //Inicio de la iteracion
        
        BENodo mejorRCL = null;
        List<BENodo> auxOptimo = null;
        List<Integer> obligatorios = null;
        for (int i=0;i<this.cantIteraciones;i++)
        {    
            //System.out.println(" iteracion "+i+": ");
            listaRecorridos.clear();
            auxOptimo = new ArrayList<BENodo>();
            BENodo partida = new BENodo();
            partida.setIdNodo(this.grafo.get(0).getIdNodo());
            partida.setDist(0);
            auxOptimo.add(partida);
            idAnterior=-1;  
            int idNodo = -1;
            obligatorios = new ArrayList<Integer>(this.nodosObligatorios);
            int auxCantObligatorio = 0;
            this.nodoActual = this.grafo.get(0);

            //bloqueados.clear();
//            for (int k=0;k<contador.length;k++)
//                contador[k] = 0;
            //System.out.println("Iteracion " + i);
            while (auxCantObligatorio != this.cantObligatorios)
            {
                
                mejorRCL = dameNodoRCL(this.nodoActual);
                while (mejorRCL==null) mejorRCL = dameNodoRCL(this.nodoActual);
                //System.out.print(" 1:"+mejorRCL.getIdNodo()+", ");

                //verficando el bloqueo de nodos
//                contador[mejorRCL.getIdNodo()-1] =contador[mejorRCL.getIdNodo()-1] +1;
//                if (contador[mejorRCL.getIdNodo()-1] == 50)
//                {
//                    System.out.println("--Bloqueado = " + mejorRCL.getIdNodo());
//                    bloqueados.add(mejorRCL.getIdNodo());
//                }

                //nodoActual.getIdNodoPadre();
                auxOptimo.add(mejorRCL);
                idNodo = mejorRCL.getIdNodo();
                int index=obligatorios.indexOf(idNodo);
                if (index>-1){
                    auxCantObligatorio++;
                    obligatorios.remove(index);
                    if (obligatorios.size()==1){
                        ultObligatorio = grafo.get(obligatorios.get(0)-1);
                    }                        
                }
//                if (obligatorios.contains(idNodo))
//                {
//                    auxCantObligatorio++;
//                    obligatorios.remove(obligatorios.indexOf(idNodo));
//                }

                //Regreso al punto inicial
                if (auxCantObligatorio == this.cantObligatorios)
                {
                    this.regresoInicio++;
                    if (this.regresoInicio == 1)
                    {
                        auxCantObligatorio--;
                        obligatorios.clear();
                        obligatorios.add(1);
                        ultObligatorio = grafo.get(obligatorios.get(0)-1);
                        //this.bloqueados.clear();
                        this.listaRecorridos.clear();
//                        for (int k=1;k<this.contador.length;k++)
//                            this.contador[k]=0;
                    }
                }

                idAnterior=nodoActual.getIdNodo();
                //if (!listaRecorridos.contains(idAnterior))
                listaRecorridos.add(idAnterior);                    
                this.nodoActual = cambiaNodoActual(idNodo);
                    //System.out.println(idAnterior+"- "+nodoActual.getIdNodo());
            }
            //System.out.println(" recorrido: ");
            //for (int k=0; k< listaRecorridos.size(); k++) 
            //    System.out.print(" "+listaRecorridos.get(k)+",");
            listaRecorridos.clear();
            if (this.Optimo == null)
                this.Optimo = auxOptimo;
            else if (dameTamanoLista(auxOptimo)<dameTamanoLista(Optimo))
                this.Optimo = auxOptimo;
            mejorRCL = null;
            this.regresoInicio=0;
            //auxOptimo = null;
        }
        
        this.rptaGrasp = this.Optimo;
        
        //Local search 2-opt        
        //return TwoOpt.TwoOpt (this.grafo, this.rptaGrasp);

        return this.rptaGrasp;
    }    
       
}
